/**
 * 
 * 给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数  。
 * 你可以对一个单词进行如下三种操作：
 * 插入一个字符
 * 删除一个字符
 * 替换一个字符
 * 
 * 0 <= word1.length, word2.length <= 500
 * word1 和 word2 由小写英文字母组成
 */

class Solution {
public:
    int minDistance(string s, string t) {
        int n = s.size(),m = t.size();
        vector dp(n + 1,vector<int>(m + 1));
        for(int j = 0;j < m;j++){
            dp[0][j + 1] = j + 1;
        }
        for(int i = 0;i < n;i++){
            dp[i + 1][0] = i + 1;
            for(int j = 0;j < m;j++){
                dp[i + 1][j + 1] = s[i] == t[j] ? dp[i][j] : min({
                    dp[i][j],dp[i + 1][j],dp[i][j + 1]
                }) + 1;
            }
        }
        return dp[n][m];
    }
};